//
// Created by francklinson on 2021/11/24 AT 10:45.
// May Saint Diana bless you!
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string> &words) {
        // 先统计牌照内的字符
        unordered_map<char, int> licenseCounter;
        for (const char &x: licensePlate) {
            if (isalpha(x)) {
                ++licenseCounter[char(tolower(x))]; // 变成小写并计数
            }
        }
        string ans(15, '#');
        for (const string &word: words) {
            if (contain(licenseCounter, word)) {
                if (word.size() < ans.size())
                    ans = word;
            }
        }
        return ans;

    }

    // 判断牌照中的字符是不是在s中都有
    bool contain(unordered_map<char, int> &licenseCounter, const string &s) {
        unordered_map<char, int> counter;
        // 统计s的字符
        for (const char &x: s) {
            ++counter[x];
        }
        for (auto &p: licenseCounter) {
            if (p.second > counter[p.first])
                return false;
        }
        return true;
    }
};

class Solution2 {
    // 直接用数组 更快点
public:
    string shortestCompletingWord(string licensePlate, vector<string> &words) {
        // 统计牌照中的字符
        vector<int> licenceCounter(26, 0);
        for (char &x: licensePlate) {
            if (isalpha(x))
                ++licenceCounter[tolower(x) - 'a'];
        }
        string ans(16, '#');
        // 对比words中的每个单词是否符合要求，并且长度最短
        for (const string &word: words) {
            if (contain(licenceCounter, word)) {
                if (word.size() < ans.size())
                    ans = word;
            }
        }
        return ans;
    }

    bool contain(vector<int> &licenceCounter, const string &s) {
        vector<int> counter(26, 0);
        for (const char &x: s) {
            if (isalpha(x))
                ++counter[tolower(x) - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (licenceCounter[i] > counter[i])
                return false;
        }
        return true;
    }
};

int main() {
    Solution2 solution;
    vector<string> words{"step", "steps", "stripe", "stepple"};
    cout << solution.shortestCompletingWord("1s3 PSt", words) << endl;
    return 0;
}

